package com.atguigui.leetcode1;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/7/10 10:04
 */
public class P16ThreeSumClosest {
    public static void main(String[] args) {


    }

    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int ans = nums[0] + nums[1] + nums[2];
            for (int i = 0; i < nums.length; i++) {
                int start = i + 1, end = nums.length - 1;
                //寻找最大最小
                while (start < end) {
                    int sum = nums[start] + nums[end] + nums[i];
                    //更新
                    if (Math.abs(target - sum) < Math.abs(target - ans)) ans = sum;
                    if (sum > target) end--;
                    else if (sum < target) start++;
                        //相等直接返回
                    else return ans;
                }
            }
            return ans;
        }
    }
}
